package com.datastructure.search.self;

import java.util.ArrayList;
import java.util.List;

public class InsertSearch {

    public static void main(String[] args) {
        int[] arr = {12,25,35,45,45,56,75};
        InsertSearch insertSearch = new InsertSearch();
        List<Integer> list = insertSearch.findTargetIndex(arr, 0, arr.length - 1, 45);
        System.out.println(list);
    }

    public List<Integer> findTargetIndex(int [] arr, int left, int right, int target){
        List<Integer> res = new ArrayList<>();
        if(left>right||target<arr[0]||target>arr[arr.length-1]){
            return res;
        }
        int mid = left + (target-arr[left])*(right-left)/(arr[right]-arr[left]);
        if(arr[mid]<target){
            return findTargetIndex(arr,mid+1,right,target);
        } else if(arr[mid]>target){
            return findTargetIndex(arr,left,right-1,target);
        } else {
            int temp = mid-1;
            while (temp >= left && arr[temp] == target) {
                res.add(temp);
                temp--;
            }
            res.add(mid);
            temp = mid + 1;
            while (temp >= left && arr[temp] == target) {
                res.add(temp);
                temp++;
            }
            return res;
        }
    }
}
